package me.zk.practice1.s;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhangkai
 * @date 2023/7/27 11:54
 */
public class LS105 {
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }

        return myBuildTree(preorder,0,preorder.length-1,0, inorder.length-1);
    }


    public TreeNode myBuildTree(int[] preorder,
                                int preLeft, int preRight,
                                int inLeft,int inRight) {
        if (preRight<preLeft) {
            return null;
        }

        //前序遍历第一个节点是根节点
        int preRootIndex = preLeft;

        //在中序遍历
        // 获取左子树根节点位置
        int inRootIndex = map.get(preorder[preRootIndex]);

        //得到左子树的数量
        int inLeftSize = inRootIndex-inLeft;

        TreeNode node = new TreeNode(preorder[preRootIndex]);

        //获取左子树位置
        node.left = myBuildTree(preorder,preRootIndex+1,preRootIndex+inLeftSize,
                inLeft,inRootIndex-1);

        node.right = myBuildTree(preorder,preRootIndex+inLeftSize+1,preRight,
                inRootIndex+1,inRight);

        return node;
    }
}
